package com.warm.base.algorithm.sort;

/**
 * @Date: 2019/9/5
 * @Author: LChuang
 * @Description: sort algorithm
 */
public class SortPart2 {

    /*#########################################################*/
    //归并排序和快速排序。这两种排序算法适合大规模的数据排序,都用到了分治思想
    //时间复杂度为O(nlogn)

    /**
     *  把数组从中间分为前后两部分，对前后两部分分别排序，排完后再合并到一起
     *  主要思想：分而治之 使用递归实现
     *
     *   非原地排序算法 -- 空间复杂度为O(n)
     *   不稳定的排序算法 -- 相邻两个大小相等的元素，排序前后顺序改变
     *   时间复杂度 -- 最好: O(nlogn)  最坏: O(nlogn)  平均: O(nlogn)
     */
    public static int[] mergeSort(int[] a){

        sort(a, 0, a.length-1);

        return a;
    }
    private static void sort(int[] a, int L, int R){
        if(L < R){
            int mid = (L + R) / 2;
            //左边
            sort(a, L, mid);
            //右边
            sort(a, mid + 1, R);
            //合并两个有序
            merge(a, L, mid, R);
        }
    }
    private static void merge(int[] a, int L, int mid, int R){
        int[] temp = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        //比较左右两个部分的元素，哪个小，把那个元素填入temp中
        while (p1 <= mid && p2 <= R){
            temp[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
        }
        //上面循环退出后，把剩余的元素依次填入到temp中
        //下面while只会有一个执行
        while (p1 <= mid){
            temp[i++] = a[p1++];
        }
        while (p2 <= R){
            temp[i++] = a[p2++];
        }
        //把最终的排序结果复制给原数组
        for (i = 0; i < temp.length; i++){
            a[L+i] = temp[i];
        }
    }

    /**
     *  随机选取数组一个元素为基准值
     *  下例子直接选取最后一位为基准，使得
     *    小于最后一个元素的值，放到数组左边
     *    大于最后一个元素的值，放到数组右边
     *    等于最后一个元素的值，放到数组中间
     *
     *  递归执行 分区 操作，直到数组有序
     */
    public static int[] quickSort(int[] a){
        sort2(a, 0, a.length-1);
        return a;
    }
    /*
    key 值变化过程:
       右->左 大于key的位置 --> 值赋给key位置
       左->右 小于key的位置 --> 值赋给上面 右->左 找到的位置
     退出循环后 把原来的 key 赋给上面 左->右 找到的位置
    完成值的交换
    */

    private static void sort2(int[] a, int low, int high){
        //递归算法出口
        if(low > high){
            return;
        }

        //定义该次排序的基准 key
        int key = a[low];
        int i = low;
        int j = high;
        //完成一次排序
        while (i < j){
            //从右往左找到第一个小于key的数
            while (i < j && a[j] >= key){
                j--;
            }
            a[i] = a[j];
            //从左往右找到第一个大于key的数
            while (i < j && a[i] <= key){
                i++;
            }
            a[j] = a[i];
        }

        //调整key的位置
        // i 值经过循环已经变化了
        a[i] = key;

        //对key左边的快排
        sort2(a,low,i-1);
        //对key右边的快排
        sort2(a,i+1, high);
    }

    public static void main(String[] args){
        int[] a = {1, 2, 8, 6, 4, 3, 7, 0, 5};
        int[] result = quickSort(a);
        for(int i = 0; i < result.length; i++){
            System.out.print(result[i]);
            System.out.print(",");
        }
    }
}
